#define _CRT_SECURE_NO_WARNINGS 1
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,-1,0,1 };
typedef pair<int, int> PII;
class Solution {
public:
    void dfs(int x, int y, vector<vector<int>>& vis, vector<vector<int>>& grid, int t, int n) {
        vis[x][y] = t;
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i];
            int b = y + dy[i];
            if (a >= 0 && a < n && b >= 0 && b < n && !vis[a][b] && grid[a][b] == 1) {
                dfs(a, b, vis, grid, t, n);
            }
        }
    }
    bool isedg(int x, int y, vector<vector<int>>& grid) {
        int n = grid.size();
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i];
            int b = y + dy[i];
            if (a >= 0 && a < n && b >= 0 && b < n && grid[a][b] == 0) {
                return true;
            }
        }
        return false;
    }
    int shortestBridge(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<int>> vis(n, vector<int>(n));

        int f = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!f && grid[i][j] == 1) {
                    dfs(i, j, vis, grid, 1, n);
                    f = 1;
                    continue;
                }
                if (f && !vis[i][j] && grid[i][j] == 1) {
                    dfs(i, j, vis, grid, 2, n);
                    f = 2;
                    break;
                }

            }
            if (f == 2)break;
        }


        queue<PII>q;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (vis[i][j] == 1 && isedg(i, j, grid)) {
                    cout << 3 << " ";
                    q.push({ i,j });
                }
                else cout << 0 << " ";
            }
            cout << endl;
        }
        // for(auto a:vis){
        //     for(auto b:a){
        //         cout<<b<<" ";
        //     }
        //     cout<<endl;
        // }
        int d = 0;
        // cout<<q.size()<<"ii"<<endl;
        int st[n][n];
        memset(st, 0, sizeof st);
        while (!q.empty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                auto it = q.front();
                q.pop();
                int x = it.first;
                int y = it.second;

                if (vis[x][y] == 2)return d - 1;
                vis[x][y] = 1;
                if (st[x][y])continue;
                st[x][y] = 1;
                for (int i = 0; i < 4; i++) {
                    int a = x + dx[i];
                    int b = y + dy[i];
                    if (a >= 0 && a < n && b >= 0 && b < n && vis[a][b] != 1 && !st[a][b]) {
                        q.push({ a,b });
                    }
                }

            }
            d++;
        }
        return d;
    }

};